//BNB omp
//$Id: bnb_omp.h 670 2011-02-27 11:52:14Z Oleg.Bulychov $
#pragma once

//__________________________________________________________________________________
#include "src/heo/include/easy_omp.h"
#include "src/heo/include/omp_alloc_init.h"
#include "solvers/bnb/bnb_common.h"
#include "solvers/bnb/bnb_balancer_random.h"
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
template<class T>
class BNB_OMP:
    public BNB<T>
{
public:
    typedef typename BNB<T>::TEnvironment TEnvironment;
    typedef typename BNB<T>::TSolution TSolution;

    typedef typename BNB<T>::TDirection TDirection;
    typedef typename BNB<T>::TCostType  TCostType;

    typedef typename BNB<T>::TTask TTask;
    typedef typename BNB<T>::TBoundPredicate TBoundPredicate;

    typedef typename TEnvironment::TSolution TInOutSolution;
    typedef typename TEnvironment::TStatistics TStatistics;
public:
    using BNB<T>::rank_;
    using BNB<T>::env_;
    using BNB<T>::rnd_;
    using BNB<T>::first_ub_;
    using BNB<T>::best_ub_;
    using BNB<T>::current_;
    using BNB<T>::pq_;
    using BNB<T>::predictor_;
    using BNB<T>::max_step_;
    using BNB<T>::BNB_CONTINUE;
    using BNB<T>::BNB_PQ_EMPTY;
    using BNB<T>::BNB_STOP;
    using BNB<T>::BNB_ERROR;
    using BNB<T>::BNB_IDLE;

protected:
    bnb_balancer<omp::recv, omp::ibsend> balancer_;
    size_t spiral_init_size_;
    int max_init_step_;

    struct BNB_Dst
    {
        int dst_;
    };
    struct BNB_Shared
    {
        TCostType best_ub_;
        volatile int ub_changed_;
        volatile int stop_;
        Array<size_t> pq_size_;
        Array<BNB_Dst> dst_;
    };
public:
    BNB_OMP():
        spiral_init_size_(),
        max_init_step_()
    {}

    template<class V>
    void accept(V& v)
    {
        v(static_cast<BNB<T>&>(*this), "/");
        v(VAR_(spiral_init_size),  8);
        v(VAR_(max_init_step),     1000);
        v(balancer_);
    }

    void solve(Solution_Pool<TInOutSolution>& pool,
        TStatistics& stat)
    {
        int np = omp_get_max_threads();
        if (1 == np)
        {//:don't bother omp
            BNB<T>::solve(pool, stat);
            return;
        }
        BNB_Shared shared = {};
        shared.pq_size_.resize(np);
        shared.dst_.resize(np);
        for (int i = 0; i < np; ++i)
            shared.dst_[i].dst_ = i;    
        omp::solver_fork< Solution_Pool<TInOutSolution>, TStatistics, BNB_OMP<T>,
            thread_alloc_init> f(pool, stat, *this);
        omp::communicator::run(np, f, shared);
    }

    void solve_OMP(Solution_Pool<TInOutSolution>& pool,
        TStatistics& stat,
        omp::communicator& comm,
        BNB_Shared& shared)
    {
        ASSERT_(this->rank_ == comm.rank());
        int np = comm.size();
        ASSERT_(np > 1);//:see above

        this->init_From_Pool(pool);
        this->calc_Max_Step();

        predictor_.init(env_, rnd_);

        int pq_init = 0;

        stat.update(0, this->rank_, *this, this->env_);

        int step = 1;
        if (0 == this->rank_)
        {//:root initialization
            if (this->get_Debug_Level())
            {
#pragma omp critical(debug_output)
                std::cout << std::setw(2)
                    << this->rank_ << ": begin BNB initialization"
                    << lf;
            }
            this->first_ub_ = this->best_ub_ = current_.get_Ub(this->env_);
            this->predictor_.pre_Calculate(this->env_, this->rnd_);

            ref_ptr<TTask> root;
            root.attach(new TTask);
            root->init(this->env_, this->rnd_);
            this->pq_.push(root);

            for (;;)
            {
                int r = this->do_Step(step);
                stat.update(step, this->rank_, *this, this->env_);
                if (r != (int)BNB_CONTINUE)
                {
                    this->show_Status(r, step);
                    break;
                }
                if (this->pq_.size() >= np * spiral_init_size_)
                {
                    pq_init = 1;
                    break;
                }
                //:max_step_ can be too big for initialization
                //:if pq_ won't grow
                if (++step > std::min(this->max_init_step_, this->max_step_))
                {
                    this->show_Status(BNB_STOP, step);
                    break;
                }
            }
            shared.best_ub_ = this->best_ub_;

            comm.barrier();
            omp::bcast(0, comm) << pq_init;

            //:spiral initialization
            if (pq_init)
            {
                omp::bcast(0, comm) << step
                    << this->first_ub_
                    << this->best_ub_
                    << this->predictor_;

                int dst = 1;
                for (size_t i = 1; i < this->pq_.size(); ++dst)
                {
                    if (dst % np == 0)
                    {
                        ++i;
                        continue;
                    }
                    omp::send ds(dst % np, comm);
                    this->send_Task(i, ds);
                    this->pq_.erase(i);
                }

                if (this->get_Debug_Level())
                {
#pragma omp critical(debug_output)
                    std::cout << std::setw(2) << this->rank_
                        << ":" << std::setw(5) << step
                        << ": BNB initialization complete"
                        << lf;
                }
            }

        }
        else
        {
            comm.barrier();
            omp::bcast(0, comm) >> pq_init;

            if (pq_init)
            {
                omp::bcast(0, comm) >> step
                    >> this->first_ub_
                    >> this->best_ub_
                    >> this->predictor_;
                //:recv tasks
                omp::recv in(0, comm);
                for (size_t i = 0; i < this->spiral_init_size_; ++i)
                {
                    this->recv_Task(in);
                }
            }
        }

        if (pq_init)
        {
            int res = main_Loop(comm, stat, shared, np, step);
            this->show_Status(res, step);
        }

        if (this->get_Debug_Level())
        {
#pragma omp critical(debug_output)
            {
                std::cout << std::setw(2) << this->rank_ << ": ";
                this->stat_.dump(std::cout);
            }
        }

        clear_OMP(comm);

        update_Pool(pool, comm, np);
    }

private:
    int main_Loop(omp::communicator& comm, TStatistics& stat, BNB_Shared& shared, int np, int& step)
    {
        int coop_rate = this->balancer_.get_Rate();
        for (; step <= this->max_step_; ++step)
        {
            int r = this->do_Step(step);
            stat.update(step, this->rank_, *this, this->env_);
            switch(r)
            {
            case BNB_ERROR:
            case BNB_STOP:
                if (!coop_rate)
                    return r;
                shared.stop_ = r;
                break;
            case BNB_PQ_EMPTY:
                if (!coop_rate)
                    return r;
                if (this->params_.debug_out_rate_ && ((this->stat_.idle_ % this->params_.debug_out_rate_) == 0))
                    show_Status(BNB_IDLE, step);
                ++this->stat_.idle_;
                break;
            default:
                break;
            }
            if (!coop_rate)
                continue;
            //if (balancer_.is_Async_Mode())
            //{
            //    reduce_UB_Async(shared, step);
            //    //TODO balancer_.balance_Async
            //    //TODO stop
            //}
            //else 
            if ((step % coop_rate) == 0)
            {
                if (shared.stop_)
                    return shared.stop_;

                reduce_UB(shared, step, np);

                if (reduce_PQ_Empty(comm, shared, np))
                    return BNB_PQ_EMPTY;

                this->balancer_.balance_Sync(*this, this->rank_, np, step,
                    comm, &shared.dst_[0]);
                bcast_UB(comm, shared, step);
            }
        }
        return BNB_STOP;
    }

    bool reduce_PQ_Empty(omp::communicator& comm, BNB_Shared& shared, int np)
    {
        //:all_gather(pq_size_, np)
        shared.pq_size_[this->rank_] = this->pq_.size();
        comm.barrier();
        for (int i = 0; i < np; ++i)
            if (shared.pq_size_[i])
                return false;
        return true;
    }

/*
    void reduce_UB_Async(BNB_Shared& shared, int step)
    {
        //:try to avoid critical section
        if (local_ub_changed_ || (shared.ub_changed_ & (1 << this->rank_)))
        {
            local_ub_changed_ = 0;
#pragma omp critical(ub_section)
            {
                if (TBoundPredicate()(best_ub_, shared.best_ub_))
                {
                    shared.best_ub_ = best_ub_;
                    shared.ub_changed_ = ~0;
//#pragma omp critical(debug_output)
//                    std::cout << this->rank_ << ":" << step << ": g_ub:= ub == " << best_ub_ << std::endl;
                }
                else if (TBoundPredicate()(shared.best_ub_, best_ub_))
                {
                    best_ub_ = shared.best_ub_;
//#pragma omp critical(debug_output)
//                    std::cout << this->rank_ << ":" << step << ": ub:= g_ub == " << shared.best_ub_ << std::endl;
                }
                shared.ub_changed_ &= ~(1 << this->rank_);
            }
        }
    }
*/

    void reduce_UB(BNB_Shared& shared, int step, int np)
    {
        if (!this->local_ub_changed_)
            return;//:try to avoid critical section
        this->local_ub_changed_ = 0;
#pragma omp critical(ub_section)
        {
            if (TBoundPredicate()(this->best_ub_, shared.best_ub_))
            {
                shared.best_ub_ = this->best_ub_;
                shared.ub_changed_ = np;
//#pragma omp critical(debug_output)
//                std::cout << this->rank_ << ":" << step << ": g_ub:= ub == " << best_ub_ << std::endl;
            }
        }
    }

    void bcast_UB(omp::communicator& comm, BNB_Shared& shared, int step)
    {
        if (!shared.ub_changed_)
            return;//:try to avoid barrier
#pragma omp atomic
        --shared.ub_changed_;

        if (TBoundPredicate()(shared.best_ub_, this->best_ub_))
        {
            this->best_ub_ = shared.best_ub_;
//#pragma omp critical(debug_output)
//            std::cout << this->rank_ << ":" << step << ": ub:= g_ub == " << shared.best_ub_ << std::endl;
        }
        comm.barrier();
    }

    void update_Pool(Solution_Pool<TInOutSolution>& pool, omp::communicator& comm, int np)
    {
        if (0 == this->rank_)
        {
            pool.sol_list_.resize(np);
        }
        comm.barrier();

        TSolution const& final_sol = this->get_Final_Solution();
        //:final_sol --> pool

        TInOutSolution& it = pool.sol_list_[this->rank_];
        it.init(this->env_, this->rnd_);
        it.assign(final_sol);

        if (this->get_Debug_Level())
        {
#pragma omp critical(debug_output)
            {
                std::cout << lf 
                          << this->rank_ << ": final cost = " << final_sol.get_Cost() << lf;
            }
        }

        comm.barrier();
    }

    void clear_OMP(omp::communicator& comm)
    {
        comm.barrier();
    }
};
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________
//__________________________________________________________________________________

//EOF!
